13th International Conference on Stochastic Programming - ICSP 2013, Bergamo (Italy). 08-12 July 2013
Summary:
Benders' decomposition has been widely applied as an efficient way of solving two-stage stochastic problems with linear recourse. Extensive research has been dedicated to improvements to this method. This presentation performs a comprehensive review of these techniques and compares them in a practical setting. The methods can be classified as modifications to the master problem and modifications to the subproblem. Within the first group, there are changes to the solution technique (such as the use of relaxed, suboptimal or alternative master solutions) and changes to the calculation of the cuts (such as alternative cut definitions and cut removal). The techniques that modify the subproblem include methods such as scenario aggregation, bunching, inexact solu-tions or incremental modelling. These techniques are concisely presented and related to the situations where they can improve the performance of a straightforward decomposition. Several of them are compared using a Transmission Expansion Planning Problem (TEP), which is particularly amenable to Benders' decomposition and that has been extensively studied with this method in the literature. The main improvement techniques that are applicable in this case are identified and implemented in several case studies of different sizes. Their performance is assessed and compared.
Publication date: 2013-07-08.
Citation:
S. Lumbreras, A. Ramos, Improvements to benders' decomposition: systematic classification and performance comparison in a transmission expansion planning problem, 13th International Conference on Stochastic Programming - ICSP 2013, Bergamo (Italy). 08-12 July 2013.
